1. Field of the Invention
This invention relates to an adder circuit, and more particularly to an adder capable of handling multiple data within a data stream without having to reconfigure the adder for different data types.
2. Description of Related Art
Most adders used today in general purpose processors are based on a conventional carry-lookahead adder (CLA). CLAs generate carry bits for all data bits simultaneously rather than one at a time and then wait for each carry bit to ripple through the adder.
The CLA generates the carry bits by using a generate bit G.sub.i and a propagate bit P.sub.i, defined as: EQU G.sub.i =A.sub.i .multidot.B.sub.i ( 1) EQU P.sub.i =A.sub.i (+)B.sub.i, (2)
where A.sub.i and B.sub.i are the respective data bits at the ith location for the two data to be added.
In these and subsequent equations, is logical AND and (+) is logical EXCLUSIVE OR.
The carry bit for the ith stage is C.sub.i =G.sub.i +P.sub.i .multidot.C.sub.i-1, where + represents a logical OR operation, which results in recursive expressions for succeeding carry bits based on an initial carry bit C.sub.-1. For a 4-bit CLA, the carry bits are: EQU C.sub.0 =G.sub.0 +P.sub.0 .multidot.C.sub.-1 ( 3) EQU C.sub.1 =G.sub.1 +P.sub.1 .multidot.G.sub.0 +P.sub.1 .multidot.P.sub.0 .multidot.C.sub.-1 ( 4) EQU C.sub.2 =G.sub.2 +P.sub.2 .multidot.G.sub.1 +P.sub.2 .multidot.P.sub.1 .multidot.G.sub.0 .multidot.C.sub.-1 ( 5) EQU C.sub.3 =G.sub.3 +P.sub.3 .multidot.G.sub.2 +P.sub.3 .multidot.P.sub.2 .multidot.G.sub.1 +P.sub.3 .multidot.P.sub.2 .multidot.P.sub.1 .multidot.G.sub.0 +P.sub.3 .multidot.P.sub.2 .multidot.P.sub.1 .multidot.P.sub.0 .multidot.C.sub.-1, (6)
where C.sub.3 is the carry out of the most significant bit (MSB) of the adder.
The result of the addition is a 5-bit sum, C.sub.3 S.sub.3 S.sub.2 S.sub.1 S.sub.0, where EQU S.sub.i =(A.sub.i (+)B.sub.i)(+)C.sub.i-1 =P.sub.i (+)C.sub.i-1.(7)
As seen from the above expressions, implementation can become costly and impractical due to the large number of fan-in and fan-out requirements when a CLA width increases to handle increasingly larger numbers. Consequently, most general purpose processors now use variations of the above scheme.
Even with the increased operational speed of carry-lookahead adders, processing greater amounts of data in shorter periods of time and simplifying logic complexity are ever-present concerns. One way to further increase processing speed is to increase the data width, i.e. increase the number of data bits that can be handled simultaneously. However, increasing the data width decreases processing efficiency when smaller data fields are used. For example, if the data width is 36 bits, but the data field or word size is 8 bits, the 8-bit words have to be aligned first for processing to begin. Furthermore, the empty data locations remain idle during processing, reducing operational efficiency.
Consequently, these empty data locations can be filled with additional data, for example, three 8-bit words, so that each 8-bit word is operated on simultaneously and independently with the other 8-bit words. However, problems arise at the boundaries of the 8-bit words. If a 36-bit adder operates on two 36-bit data streams of four 8-bit words each (A17:0!, A216:9!, A325:18!, A434:27! and B17:0!, B216:9!, B325:18!, B434:27!), the resultant 36-bit sum may not be correct if carry bits are propagated between any two adjacent 8-bit words. (Note: The 36-bit data stream used throughout the description is divided into four 9-bit groupings, with the first 8 bits being data bits, and is not meant to constitute the only type contemplated by the invention.) Therefore, carry bits must be blocked at the boundaries between each 8-bit word, i.e., at bit locations 8, 17 and 26.
A similar situation arises when two 16-bit words (A116:0! and A234:18!) are added simultaneously to another pair of 16-bit words (B116:0! and B234:18!). But now, carry bits at boundary positions 8 and 26 must be propagated, while only the carry bit at boundary position 17 is blocked. This type of adaptive gating within a data stream requires special custom designed adders to accommodate multiple data of multiple data types. Custom adders increase both the time and cost of producing multiple data type processors.
An adder circuit which can handle multiple data with multiple data types without a significant decrease in operational speed or increase in complexity is desired.